import java.util.List;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.Map;

public class GraphSearch {

	/**
	 * Searches the Graph passed in as an AdjcencyList(adjList) to find if a path exists from the start node to the goal node
	 * using General Graph Search.
	 * 
	 * Assume the AdjacencyList contains adjacent nodes of each node in the order they should be visited.
	 * 
	 * The structure(struct) passed in is an empty structure may behave as a Stack or Queue and the
	 * correspondingly search function should execute DFS(Stack) or BFS(Queue) on the graph.
	 * 
	 * @param start
	 * @param struct
	 * @param adjList
	 * @param goal
	 * @return true if path exists false otherwise
	 */
	public static <T> boolean search(T start, Structure<T> struct, Map<T, List<T>> adjList, T goal) {
		
		if (start == null || goal == null){
			return false;
		}
		
		//can't use keys outside of adjacency list
		if (!adjList.containsKey(start) || !adjList.containsKey(goal)){
			return false;
		}
		
		Set<T> visited = new HashSet<T>();
		
		struct.add(start);
		
		while(!struct.isEmpty()){
			
			T current = struct.remove();
			visited.add(current);
			System.out.println("visiting: " + current);
			
			if (current.equals(goal)){//found it
				System.out.println("found it");
				return true;
			}
			else{//add each unvisited neighbor to structure
				List<T> neighbors = adjList.get(current);
				System.out.println(current + " has " + neighbors.size() + " neighbor(s)\n");
				for (int i = 0; i < neighbors.size(); i++){
					if (!visited.contains(neighbors.get(i))){
						System.out.println("adding " + neighbors.get(i) + " to structure");
						struct.add(neighbors.get(i));
					}
				}
			}
		}
		
		//made it through loop without finding goal
		System.out.println("there's no path to " + goal);
		return false;
		
	}
	
	/**
	 * Find the shortest distance between the start node and the goal node in the given a weighted graph 
	 * in the form of an adjacency list where the edges only have positive weights
	 * Return the aforementioned shortest distance if there exists a path between the start and goal,-1
	 * otherwise.
	 * 
	 * Assume the AdjacencyList contains adjacent nodes of each node in the order they should be visited.
	 * There are no negative edge weights in the graph.
	 * 
	 * @param start
	 * @param adjList
	 * @param goal
	 * @return the shortest distance between the start and the goal node
	 */
	public static <T> int dsp(T start, Map<T, List<Pair<T, Integer>>> adjList, T goal) {
		
		ArrayList<T> unvisited = new ArrayList<T>();
		ArrayList<Integer> dist = new ArrayList<Integer>();
		
		for (T node : adjList.keySet()){
			unvisited.add(node);
		}
		
		
	}
	
	public <T> int distance(List<Pair<T, Integer>> list){
		return 1;
	}

}